package com.programmercarl.hash;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/find-all-anagrams-in-a-string/
 *
 * @author yulongtian
 * @create 2024-12-14 18:05
 */
public class Test03 {
    public static void main(String[] args) {
        Test03 test03 = new Test03();
        System.out.println(test03.findAnagrams("abab", "ab"));
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int[] count_p = new int[26];
        int[] count_s = new int[26];
        if (s.length() < p.length()) {
            return res;
        }
        for (int i = 0; i < p.length(); i++) {
            count_p[p.charAt(i) - 'a']++;
            count_s[s.charAt(i) - 'a']++;
        }
        if (check(count_p, count_s)) {
            res.add(0);
        }
        int point = 0;
        for (; point < s.length() - p.length(); point++) {
            count_s[s.charAt(point) - 'a']--;
            count_s[s.charAt(point + p.length()) - 'a']++;
            if (check(count_p, count_s)) {
                res.add(point + 1);
            }
        }

        return res;
    }

    public boolean check(int[] a, int[] b) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] != b[i]) {
                return false;
            }
        }
        return true;
    }

}
